We study provably effective and efficient data reduction for a class ofNP-hard graph modification problems based on vertex degree properties. We showfixed-parameter tractability for NP-hard graph completion (that is, edgeaddition) cases while we show that there is no hope to achieve analogousresults for the corresponding vertex or edge deletion versions. Our algorithmsare based on transforming graph completion problems into efficiently solvablenumber problems and exploiting f-factor computations for translating theresults back into the graph setting. Our core observation is that we encountera win-win situation: either the number of edge additions is small or theproblem is polynomial-time solvable. This approach helps in answering an openquestion by Mathieson and Szeider [JCSS 2012] concerning the polynomialkernelizability of Degree Constraint Edge Addition and leads to a generalmethod of approaching polynomial-time preprocessing for a wider class of degreesequence completion problems.
展开▼
